#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int maxProfit(vector<int>& prices) {
  if(prices.size()<2)
    return 0;

  int curStauts=0;  //0 for none, 1 for buy, -1 for sell
  vector<int> op(prices.size(), 0);
  int i=0;
  for(i=0; i<prices.size()-1; ++i)
  {
    if(0==curStauts)
    {
      if(prices.at(i)<prices.at(i+1))
      {
        op[i] = 1;
        curStauts = 1;
      }
      else
      {
        op[i] = 0;
        curStauts = curStauts;
      }
    }
    else if(1==curStauts)
    {
      if(prices.at(i)>prices.at(i+1))
      {
        op[i] = -1;
        curStauts = 0;
      }
      else
      {
        op[i] = 0;
        curStauts = curStauts;
      }
    }
  }
  if(0==curStauts)
    op[i] = 0;
  else
    op[i] = -1;

  int buyPrice = 0;
  int sellPrice = 0;
  int ret=0;
  for(int j=0; j<prices.size(); ++j)
  {
    if(op[j]==1)
    {
      buyPrice = prices.at(j);
    }
    else if(op[j]== -1)
    {
      sellPrice = prices.at(j);
      ret+=sellPrice - buyPrice;
    }

  }


  return ret;
        
}



int main(int argc, char* argv[]) {

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1, &tz);

  vector<int> p1={1,2,3};

  int ret = maxProfit(p1);

  cout<< "ret:" << ret << endl;

  int time2 = gettimeofday(&tv2, &tz);
  cout << "time consuming(local machine/leetcode server):" <<endl
       << "leetcode server time consuming should be less than 500ms" <<endl
       << tv2.tv_usec - tv1.tv_usec 
       << "us/" << 0.11 * ( tv2.tv_usec - tv1.tv_usec )
       << "ms" << endl;

  return 0;
}
